ABC170 D - Not Divisible

提出

code: python

from collections import Counter

n = int(input())

a = list(map(int, input().split()))

def factorization(n):

table = []

for x in range(2, int(n ** 0.5) + 1):

while n % x == 0:

table.append(x)

n //= x

if n > 1:

table.append(n)

return table

fact = []

for i in a:

fact.append(Counter(factorization(i)))

# O(N^2)になってしまう

# 1対1だから累積和ではない

print(fact)

解答

code: python

from collections import Counter

n = int(input())

a = list(map(int, input().split()))

limit = max(a) + 1

cnt = Counter(a)

# print(cnt)

# Counter({24: 1, 11: 1, 8: 1, 3: 1, 16: 1})

# 初期化。ダブっていない数字を True にセット

for a in cnt.keys():

# 候補の全ての数字について、その倍数を False にしていく

# ex.

# 24, 21, 18...は3で割り切れるから False

# 16は8で割り切れるから False

for a in cnt.keys():

for i in range(a*2, limit, a):

# あとは残っているものを数えるだけ

result = sum(not_divisible)

print(result)

テーマ

提出

code: python

n = int(input())

a = list(map(int, input().split()))

# 他のどれでも割れないAiはどれか

# 全探索では間に合わない <- 素因数分解しても同じ sort

# 最大公約数はいらない

a.sort(reverse=True)

print(a)